def fast_exponentiation(a: int, b: int, mod: int) -> int:
    result = 1
    a = a % mod  # 防止 a 很大，先做模运算
    while b > 0:
        if b % 2 == 1:  # b 是奇数
            result = (result * a) % mod
        a = (a * a) % mod  # a^2
        b //= 2  # 指数除以 2
    return result

# 测试
a = 3
b = 1000000007
mod = 1000000007
print(f"{a}^{b} mod {mod} = {fast_exponentiation(a, b, mod)}")
